package algorithms.leaning.class14;

import common.util.MyUtil;

import java.util.*;

/**
 * 实现一个并查集
 *
 * @author guichang
 * @date 2021/6/14
 */

@SuppressWarnings("all")
public class Code5_并查集_实现 {

    public static void main(String[] args) {
        List<Integer> list = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9);
        UnionFind<Integer> unionFind = new UnionFind<>(list);
        unionFind.union(1, 2);
        unionFind.union(3, 4);
        unionFind.union(5, 6);
        unionFind.union(7, 8);
        unionFind.union(2, 8);

        boolean sameSet = unionFind.isSameSet(8, 2);
        MyUtil.print(sameSet);


    }

    static class UnionFind<T> {
        /**
         * 映射关系
         */
        Map<T, Node<T>> relMap;
        /**
         * 父节点映射
         */
        Map<Node<T>, Node<T>> parentMap;
        /**
         * 代表节点的集合大小映射
         * 仅存储最顶层的父节点
         */
        Map<Node<T>, Integer> sizeMap;

        /**
         * 初始化操作
         *
         * @param list 对象列表
         */
        public UnionFind(List<T> list) {
            relMap = new HashMap<>();
            parentMap = new HashMap<>();
            sizeMap = new HashMap<>();
            for (T t : list) {
                Node<T> node = new Node<>(t);
                relMap.put(t, node);
                parentMap.put(node, node);
                sizeMap.put(node, 1);
            }
            pringMap();
        }

        /**
         * 两个对象是否在同一个集合中
         *
         * @param t1 对象1
         * @param t2 对象2
         * @return true-在同一个集合中
         */
        public boolean isSameSet(T t1, T t2) {
            // 直接判断最顶层的父节点是否相等即可
            boolean b = rootFather(relMap.get(t1)) == rootFather(relMap.get(t2));
            pringMap();
            return b;
        }

        /**
         * 合并两个集合
         *
         * @param t1 t1所在的集合
         * @param t2 t2所在的集合
         */
        public void union(T t1, T t2) {
            // 找到父节点
            Node<T> node1 = rootFather(relMap.get(t1));
            Node<T> node2 = rootFather(relMap.get(t2));
            // 两个父节点相等表示已经在同一个集合中了, 直接返回
            if (node1 == node2) {
                return;
            }
            // 节点的集合大小
            Integer sizeNode1 = sizeMap.get(node1);
            Integer sizeNode2 = sizeMap.get(node2);
            // 分出大小
            Node<T> bigNode = sizeNode1 >= sizeNode2 ? node1 : node2;
            Node<T> smallNode = bigNode == node1 ? node2 : node1;
            // 大的做头, 小的挂在大的下面
            parentMap.put(smallNode, bigNode);
            // 大头的节点数量重设
            sizeMap.put(bigNode, sizeNode1 + sizeNode2);
            // 小头消失
            sizeMap.remove(smallNode);

            pringMap();
        }

        /**
         * 集合的个数
         */
        public int setSize() {
            return sizeMap.size();
        }


        /**
         * 找到最顶层的父节点
         * 同时将 node -> rootNode 链路扁平化
         *
         * @param node 查询的节点
         * @return 最顶层的父节点
         */
        private Node<T> rootFather(Node<T> node) {
            // 记录链中所有的节点
            Deque<Node<T>> stack = new ArrayDeque<>();
            // 初始的父节点
            Node<T> rootNode = node;
            // 最顶层的节点的父节点是自己
            while (rootNode != parentMap.get(rootNode)) {
                // 加入栈中
                stack.push(rootNode);
                // 继续往上找
                rootNode = parentMap.get(rootNode);
            }
            // 将栈中的节点全挂到顶层的父节点上
            while (!stack.isEmpty()) {
                parentMap.put(stack.pop(), rootNode);
            }
            return rootNode;
        }

        private void pringMap() {
            MyUtil.print("=========================");
            MyUtil.print("parentMap: " + parentMap);
            MyUtil.print("sizeMap: " + sizeMap);
        }


        /**
         * 对象包一层
         */
        class Node<T> {
            T t;

            public Node(T t) {
                this.t = t;
            }

            @Override
            public String toString() {
                return t.toString();
            }
        }


    }


}